package leecode

func wardrobeFinishing(m int, n int, cnt int) int {
	path := make([][]bool, m)
	for i := 0; i < len(path); i++ {
		path[i] = make([]bool, n)
	}
	return backtracking130(0, 0, m, n, cnt, path)
}

func backtracking130(row, column int, m, n int, cnt int, path [][]bool) int {
	if getSum130(row)+getSum130(column) > cnt {
		return 0
	}
	//边界
	if row < 0 || row >= m || column < 0 || column >= n {
		return 0
	}
	if path[row][column] {
		return 0
	}
	path[row][column] = true
	//向右 向下
	return backtracking130(row+1, column, m, n, cnt, path) + backtracking130(row, column+1, m, n, cnt, path) + 1
}

func getSum130(num int) (sum int) {
	for num > 0 {
		sum += num % 10
		num = num / 10
	}
	return
}
